package simple;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/10/17 14:17
 */
public class No349_两个数组的交集 {
    public static void main(String[] args) {
        Solution349 solution349 = new Solution349();
        int[] nums1 = new int[]{2, 5, 2, 9, 4};
        int[] nums2 = new int[]{7, 2, 5, 5, 8, 9};

        int[] intersection = solution349.intersection(nums1, nums2);
        for (int data : intersection) {
            System.out.print(data + "\t");
        }
    }
}

class Solution349 {
    public int[] intersection(int[] nums1, int[] nums2) {
        //不排序,哈希
        Map<Integer, Boolean> map = new HashMap<>();

        //map初始化
        for (int data : nums1) {
            map.put(data, true);
        }

        List<Integer> list = new ArrayList<>();

        //nums2遍历获取map中的数是不是存在
        for (int data : nums2) {
            if (map.get(data) == null) {
                continue;
            }
            if (map.get(data)) {
                //加进来,同时置为false
                list.add(data);
                map.put(data, false);
            }
        }

        //变回去
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}


    //public int[] intersection(int[] nums1, int[] nums2) {
    //
    //    if (nums1.length == 0 || nums2.length == 0) {
    //        return new int[]{};
    //    }
    //
    //
    //    Arrays.sort(nums1);
    //    Arrays.sort(nums2);
    //
    //    //指针初始化
    //    int red = 0;
    //    int green = 0;
    //
    //    int checkRed = nums1[red];
    //    int checkGreen = nums2[green];
    //
    //    List<Integer> list = new ArrayList<>();
    //
    //    while (red < nums1.length && green < nums2.length) {
    //        boolean flag = true;
    //        while (checkRed == checkGreen) {
    //            if (flag) {
    //                list.add(checkGreen);
    //                flag = false;
    //            }
    //            green++;
    //            //判断边界条件
    //            if (green == nums2.length) {
    //                break;
    //            }
    //            checkGreen = nums2[green];
    //        }
    //
    //        //指针小,移动小指针
    //        while (checkRed < checkGreen) {
    //            red++;
    //            if (red == nums1.length) {
    //                break;
    //            }
    //            checkRed = nums1[red];
    //        }
    //
    //        while (checkRed > checkGreen) {
    //            green++;
    //            if (green == nums2.length) {
    //                break;
    //            }
    //            checkGreen = nums2[green];
    //        }
    //    }
    //
    //
    //    int[] res = new int[list.size()];
    //
    //    for (int i = 0; i < list.size(); i++) {
    //        res[i] = list.get(i);
    //    }
    //
    //    return res;
    //
    //
    //
    //}